﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Drawing;
using System.Text;


namespace ProblemsSet
{
    public static class MathLogic
    {
        #region Factorials

        private static readonly Dictionary<long, long> _factorials = new Dictionary<long, long>();
        private static long _maxFact = 0;
        private static long _maxFactValue = 1;

        public static long GetFactorial(long value)
        {
            if (_factorials.Count == 0)
            {
                _factorials.Add(0, 1);
            }
            if (_factorials.ContainsKey(value)) return _factorials[value];
            for (var i = _maxFact + 1; i <= value; i++)
            {
                _maxFactValue *= i;
                _factorials.Add(i, _maxFactValue);
            }
            _maxFact = value;
            return _maxFactValue;
        }

        #endregion

        #region Digits

        private static readonly Dictionary<long, HashSet<byte>> _digitSet = new Dictionary<long, HashSet<byte>>();
        private static readonly Dictionary<long, byte[]> _digits = new Dictionary<long, byte[]>();
        private static readonly Dictionary<long, string> _digitsArray = new Dictionary<long, string>();

        public static bool IsBouncy(long value)
        {
            var prev = value % 10;
            value /= 10;
            var isGreater = false;
            var isSmaller = false;
            while (value > 0)
            {
                var tmp = value % 10;
                value /= 10;
                if (tmp == prev)
                    continue;
                if (tmp < prev)
                {
                    if (isGreater) return true;
                    isSmaller = true;
                    prev = tmp;
                    continue;
                }
                if (tmp <= prev) continue;
                if (isSmaller) return true;
                isGreater = true;
                prev = tmp;
            }
            return false;
        }

        public static HashSet<byte> GetDigitSet(long value)
        {
            var res = new HashSet<byte>();
            if (!_digitSet.ContainsKey(value))
            {
                var tmp2 = new Dictionary<byte, int>(10);
                for (byte i = 0; i < 10; i++)
                {
                    tmp2.Add(i, 0);
                }
                var tmp = value;
                var rs = new List<byte>();
                while (value > 0)
                {
                    var q = (byte) (value%10);
                    if (!res.Contains(q))
                        res.Add(q);
                    rs.Add(q);
                    value /= 10;
                    tmp2[q]++;
                }
                var qqq = new StringBuilder();
                foreach (var pair in tmp2)
                {
                    qqq.Append(pair.Key + "*" + pair.Value + ",");
                }
                _digitsArray.Add(tmp, qqq.ToString());
                _digitSet.Add(tmp, res);
                rs.Reverse();
                _digits.Add(tmp, rs.ToArray());
                value = tmp;
            }

            return new HashSet<byte>(_digitSet[value]);
        }

        public static byte[] GetDigits(long value)
        {
            if (!_digits.ContainsKey(value)) GetDigitSet(value);
            return _digits[value];
        }

        public static long GetCountOfDigits(long value)
        {
            return GetCountOfDigits(value, false);
        }

        public static string GetHashOfDigits(long value)
        {
            if (!_digitsArray.ContainsKey(value)) GetDigitSet(value);
            return _digitsArray[value];
        }

        public static long GetCountOfDigits(long value, bool onlyDiffers)
        {
            if (onlyDiffers) return GetDigitSet(value).Count;
            return GetDigits(value).Length;
        }

        public static bool IsPolindrom(long value)
        {
            var val = GetDigits(value);
            var mid = val.Length / 2;
            for (var i = 0; i < mid; i++)
            {
                if (val[i] != val[val.Length - 1 - i]) return false;
            }
            return true;
        }

        public static long GetPolindrom(long value)
        {
            var val = GetDigits(value);
            var res = 1;
            for (var i = val.Length-1; i >=0 ;i--)
            {
                res = 10*res + val[i];
            }
            return res;
        }

        public static string GetPolindrom(string value)
        {
            var res = new StringBuilder();
            for (var i = value.Length - 1; i >= 0; i--)
            {
                res.Append(value[i]);
            }
            return res.ToString();
        }

        public static bool IsPolindrom(string value)
        {
            var val = value;
            var mid = val.Length / 2;
            for (var i = 0; i < mid; i++)
            {
                if (val[i] != val[val.Length - 1 - i]) return false;
            }
            return true;
        }

        public static List<long> GetCircular(long value)
        {
            var res = new List<long>();
            for (var i = 0; i < GetDigits(value).Length; i++)
            {
                var init = (long)(Math.Pow(10, GetDigits(value).Length-1));
                long sum = 0;
                for (var j = 0; j < GetDigits(value).Length; j++ )
                {
                    var index = i + j;
                    if (index >= GetDigits(value).Length) index -= GetDigits(value).Length;
                    sum += init*GetDigits(value)[index];
                    init /= 10;
                }
                res.Add(sum);
            }
            return res;
        }

        public static long GetSummOfDigits(long value)
        {
            long res = 0;
            while (value> 0)
            {
                res += value%10;
                value /= 10;
            }
            return res;
        }

        public static long GetDR(long value)
        {
            long res = value;
            do
            {
                res = GetSummOfDigits(res);
            } while (res > 9);
            return res;
        }

        public static long GetSummOfDigits(string value)
        {
            long res = 0;
            foreach (var c in value)
            {
                res += c - 48;
            }
            return res;
        }

        #endregion

        #region Denomenators

        private static readonly Dictionary<long, Dictionary<long, long>> _nod = new Dictionary<long, Dictionary<long, long>>();

        public static long GetNOD(long val1, long val2)
        {
            //if (_nod.ContainsKey(val1))
            //{
            //    if (_nod[val1].ContainsKey(val2))
            //        return _nod[val1][val2];
            //}
            //else
            //{
            //    _nod.Add(val1, new Dictionary<long, long>());
            //}
            //if (!_nod.ContainsKey(val2))
            //    _nod.Add(val2, new Dictionary<long, long>());
            //long tmp1 = val1;
            //long tmp2 = val2;
            while (val1 != val2)
            {
                if (val1 < val2)
                {
                    val2 -= val1;
                    continue;
                }
                val1 -= val2;
            }
            //_nod[tmp1][tmp2] = val1;
            //_nod[tmp2][tmp1] = val1;
            return val1;
        }

        #endregion

        #region Fibonacci

        private static readonly List<long> _fibonacci = new List<long>();

        public static List<long> GetFibonacci(long maxValue)
        {
            return GetFibonacci(maxValue, long.MaxValue);
        }

        public static List<long> GetFibonacci(long maxValue, long maxDigits)
        {
            if (_fibonacci.Count < 2)
            {
                _fibonacci.Add(1);
                _fibonacci.Add(1);
            }
            if (_fibonacci[_fibonacci.Count-1] >= maxValue)
            {
                for(var i = _fibonacci.Count-2; i >=0; i--)
                {
                    if (_fibonacci[i] < maxValue) return _fibonacci.GetRange(0, i);
                }
            }
            if (GetCountOfDigits(_fibonacci[_fibonacci.Count-1]) >= maxDigits)
            {
                for (var i = _fibonacci.Count - 2; i >= 0; i--)
                {
                    if (GetCountOfDigits(_fibonacci[i]) >= maxDigits) return _fibonacci.GetRange(0, i);
                }
            }

            long q;
            while ((q = _fibonacci[_fibonacci.Count - 1] + _fibonacci[_fibonacci.Count - 2]) <= maxValue)
            {
                _fibonacci.Add(q);
                if (GetCountOfDigits(q) >= maxDigits) break;
            }
            return _fibonacci;
        }

        #endregion

        #region Summs

        public static string SubstractString(string first, string second)
        {
            if (first.StartsWith("-") && !second.StartsWith("-"))
            {
                return "-"+SummString(first.Remove(0,1), second);
            }
            if (second.StartsWith("-") && !first.StartsWith("-"))
            {
                return SummString(first, second.Remove(0,1));
            }
            var sgn = "";
            if (second.StartsWith("-") && first.StartsWith("-"))
            {
                return SubstractString(second.Remove(0, 1), first.Remove(0, 1));
            }
            if (IsGreat(second, first))
            {
                return "-" + SubstractString(second, first);
            }
            var prev = 0;
            var res = new StringBuilder();
            for (var i = 0; i < Math.Max(first.Length, second.Length); i++)
            {
                var a = i < first.Length ? first[first.Length - 1 - i] - 48 : 0;
                var b = i < second.Length ? second[second.Length - 1 - i] - 48 : 0;
                a -= b + prev;
                prev = 0;
                if (a < 0)
                {
                    a += 10;
                    prev = 1;
                }
                res.Insert(0, a);
                //if (res.Length >= maxCount) return res.ToString();
            }
            if (prev > 0) res.Insert(0, prev.ToString());
            //if (res.Length > maxCount) return res.ToString().Substring(0, maxCount);
            var rs = res.ToString().TrimStart(new char[1]{'0'});
            if (rs == "") return "0";
            return rs;
        }

        public static string SummString(string first, string second, int maxCount)
        {
            if (first == null) first = "0";
            if (second == null) second = "0";
            if (first.StartsWith("-") && !second.StartsWith("-"))
            {
                first = first.Remove(0, 1);
                return SubstractString(second, first);
            }
            if (second.StartsWith("-") && !first.StartsWith("-"))
            {
                second = second.Remove(0, 1);
                return SubstractString(first, second);
            }
            var sgn = "";
            if (second.StartsWith("-") && first.StartsWith("-"))
            {
                first = first.Remove(0, 1);
                second = second.Remove(0, 1);
                sgn = "-";
            }
            var prev = 0;
            var res = new StringBuilder();
            for (var i = 0; i < Math.Max(first.Length, second.Length); i++)
            {
                var a = i < first.Length ? first[first.Length - 1 - i] - 48 : 0;
                var b = i < second.Length ? second[second.Length - 1 - i] - 48 : 0;
                a += b + prev;
                res.Insert(0, a % 10);
                prev = a / 10;
                if (res.Length >= maxCount) return sgn+res.ToString();
            }
            if (prev > 0) res.Insert(0, prev.ToString());
            return sgn+res.ToString();
        }

        public static string SummString(string first, string second)
        {
            return SummString(first, second, int.MaxValue);
        }


        public static long GetSumOfInt(IEnumerable<long> items)
        {
            long res = 0;
            foreach (var i in items)
            {
                res += i;
            }
            return res;
        }

        public static string GetSumOfIntAsString(IEnumerable<long> items)
        {
            string res = "0";
            foreach (var i in items)
            {
                res = SummString(res, i.ToString());
            }
            return res;
        }

        private static long GetSumOfInt2(IEnumerable<long> items, bool onlyEven)
        {
            long res = 0;
            foreach (var i in items)
            {
                var isEven = i % 2 == 0;
                if ((onlyEven && !isEven) || (!onlyEven && isEven)) continue;
                res += i;
            }
            return res;
        }

        public static long GetSumOfIntEven(IEnumerable<long> items)
        {
            return GetSumOfInt2(items, true);
        }

        public static long GetSumOfIntOdd(IEnumerable<long> items)
        {
            return GetSumOfInt2(items, false);
        }

        #endregion

        #region Multiplies


        public static string MultipleString(string start, long multiple, out long summDigits, int maxCount)
        {

            summDigits = 0;
            long prev = 0;
            var res = new StringBuilder();
            for (var i = start.Length - 1; i >= 0; i--)
            {
                long vl = 0;
                if (!long.TryParse(start[i].ToString(), out vl)) continue;
                vl *= multiple;
                vl += prev;
                res.Insert(0, vl % 10);
                summDigits += vl % 10;
                prev = vl / 10;
                if (res.Length >= maxCount) return res.ToString();
            }
            if (prev != 0)
            {
                res.Insert(0, prev);
                while (prev > 0)
                {
                    summDigits += prev % 10;
                    prev /= 10;
                }
            }
            //if (res.Length > maxCount) return res.ToString().Substring(0, maxCount);
            return res.ToString();
        }

        public static string MultipleString(string start, long multiple)
        {
            long tmp = 0;
            return MultipleString(start, multiple, out tmp, int.MaxValue);
        }

        public static string MultipleString(string start, long multiple, out long summDigits)
        {
            return MultipleString(start, multiple, out summDigits, int.MaxValue);
        }

        public static string MultipleString(string start, string end)
        {
            long tmp = 0;
            var res = "";
            long cnt = 0;
            var sgn = "";
            var prec = 0;
            if (start.StartsWith("-") && end.StartsWith("-"))
            {
                start = start.Remove(0, 1);
                end = end.Remove(0, 1);
            }else if (start.StartsWith("-"))
            {
                sgn = "-";
                start = start.Remove(0, 1);
            }else if (end.StartsWith("-"))
            {
                sgn = "-";
                end = end.Remove(0, 1);
            }

            if (start.IndexOf(".") >=0)
            {
                prec = start.Length - 1 - start.IndexOf(".");
                start = start.Replace(".", "");
            }
            if (end.IndexOf(".") >= 0)
            {
                prec += end.Length - 1 - end.IndexOf(".");
                end = end.Replace(".", "");
            }

            while (end.Length > 0)
            {
                var len = Math.Min(6, end.Length);
                long mult = Convert.ToInt64(end.Substring(end.Length - len, len));
                end = end.Remove(end.Length - len);
                var cur = MultipleString(start, mult);
                for (var i = 1; i <= cnt; i++)
                {
                    cur += "0";
                }
                cnt += len;
                res = SummString(res, cur);
            }

            if (prec > 0)
            {
                res = res.Insert(res.Length - prec, ".");
                res = res.TrimEnd(new char[2] {'0', '.'});
            }

            return sgn+res;
        }

        public static long GetMiltipleInt(List<long> res)
        {
            long rs = 1;
            foreach (var re in res)
            {
                rs *= re;
            }
            return rs;
        }

        public static long GetMiltipleInt(Dictionary<long, long> res)
        {
            long rs = 1;
            foreach (var re in res)
            {
                for (var i = 1; i <= re.Value; i++)
                {
                    rs *= re.Key;
                }
            }
            return rs;
        }

        #endregion

        #region Primes

        private static readonly Dictionary<long, Dictionary<long, long>> _primeFactors = new Dictionary<long, Dictionary<long, long>>();
        private static readonly List<long> _primes = new List<long>();
        private static HashSet<long> _primesSet = new HashSet<long>();

        public static List<long> GetPrimeFactorsHash(long value)
        {
            var hs = new List<long>();
            foreach (var pair in GetPrimeFactors(value))
            {
                for (var i = 0; i < pair.Value; i++)
                {
                    hs.Add(pair.Key);
                }
            }
            return hs;
        }

        public static Dictionary<long, long> GetPrimeFactors(long value)
        {
            if (_primeFactors.ContainsKey(value)) return _primeFactors[value];

            var res = new Dictionary<long, long>();
            var tmp = value;

            var factor = 2;
            while (value >= factor)
            {
                while (value % factor == 0)
                {
                    if (!res.ContainsKey(factor)) res.Add(factor, 0);
                    res[factor]++;
                    value /= factor;
                }
                if (_primeFactors.ContainsKey(value))
                {
                    foreach (var re in _primeFactors[value])
                    {
                        if (!res.ContainsKey(re.Key))
                            res.Add(re.Key, re.Value);
                        else
                            res[re.Key] += re.Value;
                    }
                    _primeFactors.Add(tmp, res);
                    return res;
                }
                factor++;
                if (factor > 3) factor++;
            }
            if (value > 1) res.Add((int)value, 1);
            _primeFactors.Add(tmp, res);
            return res;
        }

        public static List<long> GetPrimeList(long number)
        {
            return GetPrimeList(number, false);
        }

        public static bool IsPrimeNumber(long value)
        {
            return IsPrimeNumber(value, false);
        }

        public static long RS(long a, long b, long c)
        {
            if(b==0)
                return 1;
            long tmp = 0;
            if(b%2==0)
            {
                tmp = RS(a, b/2, c);
                return tmp*tmp%c;
            }
            tmp = RS(a, (b - 1)/2, c);
            return a*tmp*tmp%c;
        }

        public static bool IsPrimeNumberMiller(long value)
        {
            //var primes = new List<long>(){2,3,5,7,11,13,17,23,29};
            var primes = new List<long>() { 2, 3, 5, 7, 11, 13, 17};
            if (primes.Contains(value))
                return true;

            long y;
            long b=0;
            long m = value-1;
            while(m%2==0)
            {
            b++;
            m=m/2;
            }
            foreach (var B in primes)
            {
                y=RS(B,m,value);
                if(y==1 || y==value-1)
                    continue;
                bool ex = false;
                for(long j = 0; j <=m; j++)
                {
                    y=RS(y,2,value);
                    if(y==value-1)
                    {
                        ex = true;
                        break;
                    }
                }
                if (!ex)
                    return false;
            }
            return true;
        }

        public static bool IsPrimeNumber(long value, bool onlySet)
        {
            if (_primes.Count < 1) GetPrimeList(2);
            if (_primesSet.Contains(value)) return true;
            if (onlySet) return false;
            if (value < _primes[_primes.Count-1]) return false;
            if (value == 2 || value == 3) return true;
            if (value % 2 == 0) return false;
            if (value % 3 == 0) return false;
            var proved = Math.Sqrt(value);
            foreach (var l in _primesSet)
            {
                if (l > proved) return true;
                if (value % l == 0) return false;
            }
            var init = _primes.Count > 0 ? _primes[_primes.Count - 1] + 2 : 5;
            init = Math.Max(init, 5);
            for (var i = init; i <= proved; i= i+2 )
            {
                if (value % i == 0) return false;
            }
            return true;
        }

        public static List<long> GetPrimeList(long number, bool isMaxPrime)
        {
            long current = 2;
            if (_primes.Count > 0) current = _primes[_primes.Count - 1] + 1;
            if (current >= 4 && current%2==0) current++;
            if (!isMaxPrime)
            {
                if (_primes.Count >= number)
                {
                    return _primes.GetRange(0, (int)number);
                }
                while (_primes.Count < number)
                {
                    var ex = false;
                    var sq = Math.Sqrt(current);
                    foreach (var l in _primes)
                    {
                        if (l > sq) break;
                        if (current % l != 0) continue;
                        ex = true;
                        break;
                    }
                    if (!ex) _primes.Add(current);
                    current++;
                    if (current > 3) current++;
                }
                _primesSet = new HashSet<long>(_primes);
                return _primes;
            }
            if (_primes.Count > 0 && _primes[_primes.Count - 1] == number) return _primes;
            if (_primes.Count > 0 && _primes[_primes.Count-1] > number)
            {
                for (var i = _primes.Count - 2; i >= 0; i--)
                {
                    if (_primes[i] < number) return _primes.GetRange(0, i+1);
                }
            }

            while (true)
            {
                var ex = false;
                var sq = Math.Sqrt(current);
                foreach (var l in _primes)
                {
                    if (l > sq) break;
                    if (current % l != 0) continue;
                    ex = true;
                    break;
                }
                if (!ex) _primes.Add(current);
                current++;
                if (current > 3) current++;
                if (current >= number) break;
            }
            _primesSet = new HashSet<long>(_primes);
            return _primes;
        }

        public static bool IsPrimesRemarkable(long value1, long value2)
        {
            return IsPrimesRemarkable(value1, value2, false);
        }

        public static bool IsPrimesRemarkable(long value1, long value2, bool onlySet)
        {
            var q1 = (int)Math.Log10(value1) + 1;
            var q2 = (int)Math.Log10(value2) + 1;

            var tmp = (long)(value1 + value2 * (long)Math.Pow(10, q1));

            if (!IsPrimeNumber(tmp, onlySet))
            {
                return false;
            }
            tmp = (long)(value2 + value1 * (long)Math.Pow(10, q2));
            if (!IsPrimeNumber(tmp, onlySet))
            {
                return false;
            }
            return true;
        }

        #endregion

        #region Strings

        public static bool IsAnagram(string value1, string value2)
        {
            if (value1.Length != value2.Length) return false;
            foreach (var c in value1)
            {
                var tmp = value2.IndexOf(c);
                if (tmp == -1) return false;
                value2 = value2.Remove(tmp, 1);
            }
            return true;
        }

        public static string GetSimpleSqrt(string value, long count)
        {
            var a = MultipleString(value, 5);
            var b = "5";
            while (b.Length < value.Length+count+2)
            {
                if (IsGreat(b, a))
                {
                    a += "00";
                    b = b.Insert(b.Length - 1, "0");
                }
                else
                {
                    a = SubstractString(a, b);
                    b = SummString(b, "10");
                }
            }
            return b;
        }

        public static string DivideStrings(string start, string end, long count)
        {
            var res = "";
            var sgn = "";
            var prec = 0;
            if (start.StartsWith("-") && end.StartsWith("-"))
            {
                start = start.Remove(0, 1);
                end = end.Remove(0, 1);
            }else if (start.StartsWith("-"))
            {
                sgn = "-";
                start = start.Remove(0, 1);
            }else if (end.StartsWith("-"))
            {
                sgn = "-";
                end = end.Remove(0, 1);
            }

            if (start.IndexOf(".") >=0)
            {
                prec = start.Length - 1 - start.IndexOf(".");
                start = start.Replace(".", "");
            }
            if (end.IndexOf(".") >= 0)
            {
                prec -= end.Length - 1 - end.IndexOf(".");
                end = end.Replace(".", "");
            }
            var pointExists = false;
            while (res.Length < start.Length-end.Length+count+3)
            {
                bool isFirst = true;
                var ln = Math.Min(end.Length, start.Length);
                while (IsGreat(end, start.Substring(0, ln)))
                {
                    if (start.Replace("0","") == "")
                        return sgn + res + start.Substring(0, start.Length-ln);
                    ln++;
                    if (start.Length < ln)
                    {
                        start += "0";
                        if (!pointExists)
                        {
                            if (res.Length == 0) res += "0.";
                            else res += ".";
                            pointExists = true;
                        }
                    }
                    
                    if (isFirst)
                    {
                        isFirst = false;
                        continue;
                    }
                    res+="0";

                }
                var kf = 1;
                for (var a = 2; a < 10; a++ )
                {
                    if (IsGreat(MultipleString(end, a), start.Substring(0, ln))) break;
                    kf = a;
                }

                res += kf;
                var tmp = SubstractString(start.Substring(0, ln), MultipleString(end, kf));
                start = tmp + start.Remove(0, ln);
            }
            if (prec > 0)
            {
                var idx = res.IndexOf(".");
                if (idx == -1) idx = res.Length;
                var real = idx - prec;
                if (real <= 0)
                {
                    for (var i = 1; i <= -real + 1; i++)
                    {
                        res = "0" + res;
                    }
                    real = 1;
                }
                res = res.Insert(real, ".");
                res = res.TrimEnd(new char[2] {'0', '.'});
            }
            return sgn + res;
        }

        public static string GetSqrt(string value, long prec)
        {
            for (var i = 1; i <= prec*2; i++)
            {
                value += "0";
            }
            var cur = "1";
            var res = "0";
            while (true)
            {
                value = SubstractString(value, cur);
                if (value.StartsWith("-")) break;
                res = SummString(res, "1");
                if (value == "0") break;
                cur = SummString(cur, "2");
            }
            res = res.Insert((int)(res.Length - prec), ".");
            res = res.TrimEnd(new char[2] {'0', '.'});
            return res;
        }

        public static string FindNextFactByDigits(string value)
        {
            var res = "0";
            foreach (var c in value)
            {
                res = SummString(res, GetFactorial(c - 48).ToString());
            }
            return res;
        }

        public static bool IsNonRepeating(ref List<string> list, long max)
        {
            while (list.Count <= max)
            {
                string tmp = FindNextFactByDigits(list[list.Count - 1]);
                if (list[0] == tmp)
                    return true;
                if (list.Contains(tmp))
                    return false;
                list.Add(tmp);
            }
            return false;
        }


        public static bool IsGreat(string value1, string value2)
        {
            value1 = value1.TrimStart(new char[1] {'0'});
            value2 = value2.TrimStart(new char[1] { '0' });
            if (value1.Length != value2.Length) return value1.Length > value2.Length;
            for (var i = 0; i < value1.Length; i++)
            {
                if (value1[i] != value2[i]) return value1[i] > value2[i];
            }
            return false;
        }

        public static void FormeString(ref List<string> result, string begin, string leaved, int max)
        {
            FormeString(ref result, begin, leaved, max, int.MaxValue);
        }

        public static void FormeString(ref List<string> result, string begin, string leaved, int max, int maxLength)
        {
            if (result.Count >= max) return;
            if (begin.Length >= maxLength)
            {
                result.Add(begin);
                return;
            }
            for (var i = 0; i < leaved.Length; i++ )
            {
                var c = leaved[i];
                if (leaved.Length == 1)
                {
                    result.Add(begin + c);
                    return;
                }
                FormeString(ref result, begin + c, leaved.Remove(i,1), max, maxLength);
            }
        }

        public static long GetScoreString(string value)
        {
            value = value.ToUpper();
            long res = 0;
            foreach (var c in value)
            {
                res += c - 64;
            }
            return res;
        }

        public static HashSet<string> GetMasks(string init, long count)
        {
            var res = new HashSet<string>();
            if (count >= init.Length) return res;
            GetMasksRec(ref res, init, 0, count);
            return res;
        }

        private static void GetMasksRec(ref HashSet<string> result, string begin, int index, long count)
        {
            if (count == 0)
            {
                result.Add(begin);
                return;
            }
            if (index + count >= begin.Length) return;
            GetMasksRec(ref result, begin, index+1, count);
            GetMasksRec(ref result, begin.Remove(index,1).Insert(index,"*"), index + 1, count-1);
        }

        public static List<string> GetBrutForce(string init, long length)
        {
            var res = new List<string>();
            MakeBrutForce(ref res, ref init, length-1, "");
            return res;
        }

        private static void MakeBrutForce(ref List<string> result, ref string init, long index, string res)
        {
            if (index < 0)
            {
                result.Add(res);
                return;
            }
            foreach (var c in init)
            {
                MakeBrutForce(ref result, ref init, index-1, c+res);
            }
        }

        #endregion

        #region Seq

        public static BigInteger[][] GetFibonacciSeq(long max)
        {
            var real = new BigInteger[max][];
            long index = 0;
            for (int i = 0; i < max; i++)
            {
                real[i] = new BigInteger[max];
                for (int j = 0; j < max; j++)
                {
                    index++;
                    BigInteger tmp = 0;
                    if (index <= 55)
                        tmp =  (100003 - 200003 * index + 300007 * index * index * index) % 1000000 - 500000;
                    else
                    {
                        var pt1 = GetPointByIndex(max, index-24);
                        var pt2 = GetPointByIndex(max, index-55);
                        tmp = (real[pt1.X][pt1.Y] + real[pt2.X][pt2.Y] + 1000000) % 1000000 - 500000;
                    }
                    
                    real[i][j] = tmp;
                }
            }
            return real;
        }

        private static Point GetPointByIndex(long max, long index)
        {
            return new Point((int)((index-1)/max), (int)((index-1) % max));
        }

        private static long GetIndexByPoint(long max, long x, long y)
        {
            return max*y+x+1;
        }


        //public static BigInteger GetFibonacciSeq(BigInteger index)
        //{
        //    if (index <= 55)
        //        return (100003 - 200003 * index + 300007 * index * index * index) % 1000000 - 500000;
        //    return (GetFibonacciSeq(index - 24) + GetFibonacciSeq(index - 55) + 1000000)%1000000 - 500000;
        //}

        public static long GetTriangle(long index)
        {
            return index * (index + 1) / 2;
        }

        public static long GetSquare(long index)
        {
            return index * index;
        }

        public static long GetPenta(long index)
        {
            return index * (3 * index - 1) / 2;
        }

        public static long GetHexa(long index)
        {
            return index * (2 * index - 1);
        }

        public static long GetHepta(long index)
        {
            return index * (5 * index - 3)/2;
        }

        public static long GetOcta(long index)
        {
            return index * (3 * index - 2);
        }

        public static bool IsTriangle(long value)
        {
            double val = (-1 + Math.Sqrt(1 + 8 * value)) / 2;
            return val == Math.Truncate(val);
        }

        public static bool IsSquare2(long value)
        {
            var val = (long)(Math.Sqrt(value));
            return val*val == value;
        }

        public static bool IsSquare2(ulong value)
        {
            var val = (ulong)(Math.Sqrt(value));
            return val * val == value;
        }

        public static bool IsSquare(long value)
        {
            double val = (Math.Sqrt(value));
            return val == Math.Truncate(val);
        }

        public static bool IsPenta(long value)
        {
            double val = (1 + Math.Sqrt(1 + 24 * value)) / 6;
            return val == Math.Truncate(val);
        }

        public static bool IsHexa(long value)
        {
            double val = (1 + Math.Sqrt(1 + 8 * value)) / 4;
            return val == Math.Truncate(val);
        }

        public static bool IsHepta(long value)
        {
            double val = (3 + Math.Sqrt(9 + 40*value))/10;
            return val == Math.Truncate(val);
        }

        public static bool IsOcta(long value)
        {
            double val = (2 + Math.Sqrt(4 + 12 * value)) / 6;
            return val == Math.Truncate(val);
        }

        #endregion

        #region Combinatoric

        private static readonly Dictionary<Point, string> _j = new Dictionary<Point, string>();

        private static string GetJ(long n, long k)
        {
            if (n < k) return "0";
            if (n == k) return "1";
            if (k == 1) return "1";
            var ptn = new Point((int) n, (int) k);
            if (_j.ContainsKey(ptn)) return _j[ptn];
            var res = SummString(GetJ(n-1, k-1), GetJ(n-k,k));
            _j.Add(ptn, res);
            return res;
        }

        public static long GetCountOfFormedSumm(long value)
        {
            return GetCountOfFormedSumm(value, false);
        }

        public static string GetCountOfFullFormedSumm(long value)
        {
            return GetJ(2*value, value);
        }

        public static long GetCountOfFormedSumm(long value, bool onlyPrimes)
        {
            if (!onlyPrimes)
            {
                return Convert.ToInt64(GetJ(2*value, value))-1;
            }
            if (onlyPrimes)
            {
                GetPrimeList(value, true);
            }
            long res = 0;
            FormeSumm(ref res, value - 1, value, onlyPrimes);
            return res;
        }

        private static void FormeSumm(ref long count, long prev, long leave, bool onlyPrimes)
        {
            for (var i = Math.Min(leave, prev); i >= 1; i--)
            {
                if (onlyPrimes && !IsPrimeNumber(i, true)) continue;
                if (leave - i == 0)
                {
                    count++;
                    continue;
                }
                FormeSumm(ref count, i, leave - i, onlyPrimes);
            }
        }

        public static long GetC(long k, long n)
        {
            return GetC(k, n, long.MaxValue);
        }

        public static long GetC(long k, long n, long max)
        {
            if (k >= n) return 1;
            long res = 1;
            var divs = new List<long>();
            var mx = Math.Max(k, n - k);
            var mn = Math.Min(k, n-k);
            for (var i = 2; i <= mn; i++)
            {
                divs.Add(i);
            }
            for (var i = mx + 1; i <= n; i++)
            {
                res *= i;
                var tmp = new List<long>(divs);
                foreach (var l in tmp)
                {
                    if (res % l != 0) continue;
                    res /= l;
                    divs.Remove(l);
                }
                if (tmp.Count == 0 && res > max) return res;
            }
            foreach (var l in divs)
            {
                res /= l;
                //divs.Remove(l);
            }
            return res;
        }

        public static double GetC(long k, long n, long max, bool isDouble)
        {
            if (k >= n) return 1;
            double res = 1;
            var divs = new List<long>();
            var mx = Math.Max(k, n - k);
            var mn = Math.Min(k, n - k);
            for (var i = 2; i <= mx; i++)
            {
                divs.Add(i);
            }
            for (var i = mn + 1; i <= n; i++)
            {
                res *= i;
                var tmp = new List<long>(divs);
                foreach (var l in tmp)
                {
                    //if (res % l != 0) continue;
                    res /= l;
                    divs.Remove(l);
                    break;
                }
                if (tmp.Count == 0 && res > max) return res;
            }
            foreach (var l in divs)
            {
                res /= l;
                //divs.Remove(l);
            }
            return res;
        }

        public static List<List<long>> GetCombinations(ref List<long> values, long count)
        {
            var result = new List<List<long>>();
            GetCombinationsRec(ref result, new List<long>(), values, count);
            return result;
        }

        private static void GetCombinationsRec(ref List<List<long>> result, List<long> current, List<long> leaved, long count)
        {
            if (count == 0)
            {
                result.Add(current);
                return;
            }
            foreach (var l in leaved)
            {
                if (!current.Contains(l))
                {
                    var tmp = new List<long>(current);
                    tmp.Add(l);
                    var tmp2 = new List<long>(leaved);
                    tmp2.Remove(l);
                    GetCombinationsRec(ref result, tmp, tmp2, count-1);
                }
            }
        }

        public static long GetCountRows(long length, long val)
        {
            var _rows = new Dictionary<long, long>();
            return GetCountRows(ref _rows, length, val);
        }

        public static long GetCountRows(ref Dictionary<long, long> _rows, long length, long val)
        {
            return GetCountRows(ref _rows, length, val, true);
        }

        public static long GetCountRows(ref Dictionary<long, long> _rows, long length, long val, bool useSpace)
        {
            var tmp = useSpace ? 1 : 0;
            if (length < -tmp) return 0;
            if (length < val) return 1;
            if (length == val) return 2;
            if (_rows.ContainsKey(length)) return _rows[length];
            long res = 1;
            for (long sl = val; sl <= length; sl++)
            {
                for (long sp = 0; sp <= length-sl; sp++)
                {
                    res += GetCountRows(ref _rows, length - sl - tmp - sp, val, useSpace);
                }
            }
            _rows.Add(length, res);
            return res;
        }

        public static long GetCountRows(long length, List<long> vals, bool useSpace)
        {
            var _rows = new Dictionary<long, long>();
            return GetCountRows(ref _rows, length, vals);
        }

        public static long GetCountRows(long length, List<long> vals)
        {
            var dct = new Dictionary<long, long>();
            return GetCountRows(ref dct, length, vals);
        }

        private static long GetCountRows(ref Dictionary<long, long> _rows, long length, List<long> vals)
        {
            if (length < 0) return 0;
            if (length == 0) return 1;
            if (_rows.ContainsKey(length)) return _rows[length];
            long res = 1;
            if (length == 1)
            {
                foreach (var l in vals)
                {
                    if ( l== 1)
                        res++;
                }
                _rows.Add(1,res);
                return res;
            }

            res = GetCountRows(ref _rows, length - 1, vals);
            foreach (var l in vals)
            {
                res += GetCountRows(ref _rows, length - l, vals);
            }
            _rows.Add(length, res);
            return res;

            //if (length < -1) return 0;
            //if (length <= 0) return 1;
            //if (_rows.ContainsKey(length)) return _rows[length];
            //long res = 0;
            //foreach (var sl in vals)
            //{
            //    if (length >= sl)
            //    {
            //        res += 1;
            //        break;
            //    }
            //}
            //if (res == 0) return 1;
            //res = 0;
            //foreach (var sl in vals)
            //{
            //    for (long sp = 0; sp <= length - sl +1; sp++)
            //    {
            //        res += GetCountRows(ref _rows, length - sl - sp, vals);
            //    }
            //}
            //_rows.Add(length, res);
            //return res;
        }

        #endregion

        #region Poker

        private interface IPokerHand : IComparable
        {
            int Koef { get; set; }
            bool IsAllow { get; set; }
        }

        public class PokerCard: IComparable
        {
            public char Value { get; set; }
            public char Suit { get; set; }
            public int IntValue { get; set; }
            public int IntSuit { get; set; }
            public int Position { get; set; }

            public PokerCard(string init)
            {
                Suit = ' ';
                Value = ' ';
                if (init == null) init = "  ";
                if (init.Length < 2) init += " ";
                init = init.ToUpper();
                Suit = init[1];
                Value = init[0];
                switch (Value)
                {
                    case '2':
                        {
                            IntValue = 20;
                            break;
                        }
                    case '3':
                        {
                            IntValue = 30;
                            break;
                        }
                    case '4':
                        {
                            IntValue = 40;
                            break;
                        }
                    case '5':
                        {
                            IntValue = 50;
                            break;
                        }
                    case '6':
                        {
                            IntValue = 60;
                            break;
                        }
                    case '7':
                        {
                            IntValue = 70;
                            break;
                        }
                    case '8':
                        {
                            IntValue = 80;
                            break;
                        }
                    case '9':
                        {
                            IntValue = 90;
                            break;
                        }
                    case 'T':
                        {
                            IntValue = 100;
                            break;
                        }
                    case 'J':
                        {
                            IntValue = 110;
                            break;
                        }
                    case 'Q':
                        {
                            IntValue = 120;
                            break;
                        }
                    case 'K':
                        {
                            IntValue = 130;
                            break;
                        }
                    case 'A':
                        {
                            IntValue = 140;
                            break;
                        }
                    default:
                        {
                            IntValue = 0;
                            break;
                        }
                }
                switch (Suit)
                {
                    case 'H':
                        {
                            IntSuit = 1;
                            break;
                        }
                    case 'C':
                        {
                            IntSuit = 2;
                            break;
                        }
                    case 'S':
                        {
                            IntSuit = 3;
                            break;
                        }
                    case 'D':
                        {
                            IntSuit = 4;
                            break;
                        }
                    default:
                        {
                            IntSuit = 0;
                            break;
                        }
                }
                Position = IntSuit + IntValue;
            }

            public int CompareTo(object obj)
            {
                var comp = obj as PokerCard;
                if (comp != null)
                {
                    return Position.CompareTo(comp.Position);
                }
                return -1;
            }
        }

        public class PokerHand: IPokerHand
        {
            public int Koef { get; set; }

            public virtual int CompareTo(object obj)
            {
                return -1;
            }

            public bool IsAllow {get; set;}
        }

        public class Poker_RoyalFlush: PokerHand
        {
            public Poker_RoyalFlush(ref List<PokerCard> cards)
            {
                Koef = 0;

                IsAllow = false;
                if (cards.Count < 5) return;
                if (cards[0].IntValue != 100 || cards[4].IntValue != 140) return;
                var q = cards[0].IntSuit;
                foreach (var s in cards)
                {
                    if (q != s.IntSuit) return;
                }
                cards.Clear();
                IsAllow = true;
                Koef = 10;
            }

            public override int CompareTo(object obj)
            {
                var q = obj as IPokerHand;
                if (q == null) return 1;
                if (q.Koef != Koef) return Koef.CompareTo(q.Koef);
                if (!IsAllow && !q.IsAllow) return 0;
                if (!IsAllow && q.IsAllow) return 0;
                return 1;
            }

        }

        public class Poker_StraightFlush : PokerHand
        {
            public PokerCard StartCard { get; set; }

            public Poker_StraightFlush(ref List<PokerCard> cards)
            {
                Koef = 0;
                IsAllow = false;
                 if (cards.Count < 5) return;
                for (var i = 1; i < 5; i++)
                {
                    if (cards[i].Position - cards[i-1].Position != 10) return;
                }
                StartCard = cards[0];
                cards.Clear();
                IsAllow = true;
                Koef = 9;
            }

            public int CompareTo(object obj)
            {
                var q = obj as IPokerHand;
                if (q == null) return 1;
                if (q.Koef != Koef) return Koef.CompareTo(q.Koef);
                if (!IsAllow && !q.IsAllow) return 0;
                if (!IsAllow && q.IsAllow) return 0;
               
                var qq = obj as Poker_StraightFlush;
                return qq == null ? 1 : StartCard.IntValue.CompareTo(qq.StartCard.IntValue);
            }

        }

        public class Poker_FourOfKind : PokerHand
        {
            public PokerCard StartCard { get; set; }

            public Poker_FourOfKind(ref List<PokerCard> cards)
            {
                IsAllow = false;
                Koef = 0;

                if (cards.Count < 4) return;

                var dct = new Dictionary<int, List<PokerCard>>();
                foreach (var card in cards)
                {
                    if (!dct.ContainsKey(card.IntValue))
                    {
                        dct.Add(card.IntValue, new List<PokerCard>());
                    }
                    dct[card.IntValue].Add(card);
                    if (dct[card.IntValue].Count != 4) continue;
                    StartCard = card;
                    foreach (var pokerCard in dct[card.IntValue])
                    {
                        cards.Remove(pokerCard);
                    }
                    IsAllow = true;
                    Koef = 8;
                    return;
                }
            }

            public int CompareTo(object obj)
            {
                var q = obj as IPokerHand;
                if (q == null) return 1;
                if (q.Koef != Koef) return Koef.CompareTo(q.Koef);
                if (!IsAllow && !q.IsAllow) return 0;
                if (!IsAllow && q.IsAllow) return 0;

                var qq = obj as Poker_FourOfKind;
                return qq == null ? 1 : StartCard.IntValue.CompareTo(qq.StartCard.IntValue);
            }


        }

        public class Poker_FullHouse : PokerHand
        {
            public PokerCard ThreeCard { get; set; }
            public PokerCard PaarCard { get; set; }

            public Poker_FullHouse(ref List<PokerCard> cards)
            {
                IsAllow = false;
                Koef = 0;

                if (cards.Count < 5) return;
                var dct = new Dictionary<int, List<PokerCard>>();
                foreach (var card in cards)
                {
                    if (!dct.ContainsKey(card.IntValue))
                    {
                        dct.Add(card.IntValue, new List<PokerCard>());
                    }
                    dct[card.IntValue].Add(card);
                    if (dct.Count > 2) return;
                }
                foreach (var pair in dct)
                {
                    if (pair.Value.Count == 3)
                    {
                        ThreeCard = pair.Value[0];
                        continue;
                    }
                    if (pair.Value.Count == 2)
                    {
                        PaarCard = pair.Value[0];
                        continue;
                    }
                    return;
                }
                cards.Clear();
                IsAllow = true;
                Koef = 7;
            }

            public int CompareTo(object obj)
            {
                var q = obj as IPokerHand;
                if (q == null) return 1;
                if (q.Koef != Koef) return Koef.CompareTo(q.Koef);
                if (!IsAllow && !q.IsAllow) return 0;
                if (!IsAllow && q.IsAllow) return 0;

                var qq = obj as Poker_FullHouse;
                if  (qq == null) return 1;
                if (ThreeCard.IntValue != qq.ThreeCard.IntValue) return ThreeCard.IntValue.CompareTo(qq.ThreeCard.IntValue);
                return PaarCard.IntValue.CompareTo(qq.PaarCard.IntValue);
            }

        }

        public class Poker_Flush : PokerHand
        {
            public PokerCard StartCard { get; set; }

            public Poker_Flush(ref List<PokerCard> cards)
            {
                Koef = 0;
                IsAllow = false;

                if (cards.Count < 5) return;

                StartCard = cards[0];
                for (var i = 1; i < 5; i++)
                {
                    if (StartCard.IntSuit != cards[i].IntSuit) return;
                    if (StartCard.IntValue < cards[i].IntValue) StartCard = cards[i];
                }
                
                cards.Clear();
                IsAllow = true;
                Koef = 6;
            }

            public int CompareTo(object obj)
            {
                var q = obj as IPokerHand;
                if (q == null) return 1;
                if (q.Koef != Koef) return Koef.CompareTo(q.Koef);
                if (!IsAllow && !q.IsAllow) return 0;
                if (!IsAllow && q.IsAllow) return 0;

                var qq = obj as Poker_Flush;
                return qq == null ? 1 : StartCard.IntValue.CompareTo(qq.StartCard.IntValue);
            }


        }

        public class Poker_Straight : PokerHand
        {
            public PokerCard StartCard { get; set; }

            public Poker_Straight(ref List<PokerCard> cards)
            {
                Koef = 0;
                IsAllow = false;

                if (cards.Count < 5) return;

                StartCard = cards[0];
                for (var i = 1; i < 5; i++)
                {
                    if (cards[i].IntValue - cards[i-1].IntValue != 10) return;
                }
                
                cards.Clear();
                IsAllow = true;
                Koef = 5;
            }

            public int CompareTo(object obj)
            {
                var q = obj as IPokerHand;
                if (q == null) return 1;
                if (q.Koef != Koef) return Koef.CompareTo(q.Koef);
                if (!IsAllow && !q.IsAllow) return 0;
                if (!IsAllow && q.IsAllow) return 0;

                var qq = obj as Poker_Straight;
                return qq == null ? 1 : StartCard.IntValue.CompareTo(qq.StartCard.IntValue);
            }

        }

        public class Poker_ThreeOfKind : PokerHand
        {
            public PokerCard StartCard { get; set; }

            public Poker_ThreeOfKind(ref List<PokerCard> cards)
            {
                Koef = 0;
                IsAllow = false;

                if (cards.Count < 3) return;

                var dct = new Dictionary<int, List<PokerCard>>();
                foreach (var card in cards)
                {
                    if (!dct.ContainsKey(card.IntValue))
                    {
                        dct.Add(card.IntValue, new List<PokerCard>());
                    }
                    dct[card.IntValue].Add(card);
                    if (dct.Count > 3) return;
                    foreach (var pair in dct)
                    {
                        if (pair.Value.Count != 3) continue;
                        foreach (var pokerCard in pair.Value)
                        {
                            cards.Remove(pokerCard);
                            StartCard = pokerCard;
                        }
                        IsAllow = true;
                        Koef = 4;
                        return;
                    }
                }
            }

            public int CompareTo(object obj)
            {
                var q = obj as IPokerHand;
                if (q == null) return 1;
                if (q.Koef != Koef) return Koef.CompareTo(q.Koef);
                if (!IsAllow && !q.IsAllow) return 0;
                if (!IsAllow && q.IsAllow) return 0;

                var qq = obj as Poker_ThreeOfKind;
                return qq == null ? 1 : StartCard.IntValue.CompareTo(qq.StartCard.IntValue);
            }

        }

        public class Poker_TwoPairs : PokerHand
        {
            public PokerCard FirstCard { get; set; }
            public PokerCard SecondCard { get; set; }

            public Poker_TwoPairs(ref List<PokerCard> cards)
            {
                Koef = 0;
                IsAllow = false;
                FirstCard = new PokerCard("  ");
                SecondCard = new PokerCard("  ");

                if (cards.Count < 4) return;

                var dct = new Dictionary<int, List<PokerCard>>();
                foreach (var card in cards)
                {
                    if (!dct.ContainsKey(card.IntValue))
                    {
                        dct.Add(card.IntValue, new List<PokerCard>());
                    }
                    dct[card.IntValue].Add(card);
                    if (dct.Count > 3) return;
                }

                var removed = new List<PokerCard>();
                foreach (var pair in dct)
                {
                    if (pair.Value.Count == 2)
                    {
                        if (removed.Count == 0)
                        {
                            FirstCard = pair.Value[0];
                        }
                        else
                        {
                            SecondCard = pair.Value[0];
                        }
                        foreach (var card in pair.Value)
                        {
                            removed.Add(card);
                        }
                    }
                }
                if (removed.Count != 4) return;

                foreach (var card in removed)
                {
                    cards.Remove(card);
                }

                IsAllow = true;
                Koef = 3;
            }


            public int CompareTo(object obj)
            {
                var q = obj as IPokerHand;
                if (q == null) return 1;
                if (q.Koef != Koef) return Koef.CompareTo(q.Koef);
                if (!IsAllow && !q.IsAllow) return 0;
                if (!IsAllow && q.IsAllow) return 0;

                var qq = obj as Poker_TwoPairs;
                return qq == null ? 1 : (FirstCard.IntValue + SecondCard.IntValue).CompareTo(qq.FirstCard.IntValue + qq.SecondCard.IntValue);
            }

        }

        public class Poker_OnePair : PokerHand
        {
            public PokerCard StartCard { get; set; }

            public Poker_OnePair(ref List<PokerCard> cards)
            {
                Koef = 0;
                IsAllow = false;

                if (cards.Count < 2) return;

                var dct = new Dictionary<int, List<PokerCard>>();
                foreach (var card in cards)
                {
                    if (!dct.ContainsKey(card.IntValue))
                    {
                        dct.Add(card.IntValue, new List<PokerCard>());
                    }
                    dct[card.IntValue].Add(card);
                    foreach (var pair in dct)
                    {
                        if (pair.Value.Count != 2) continue;
                        StartCard = pair.Value[0];
                        foreach (var pokerCard in pair.Value)
                        {
                            cards.Remove(pokerCard);
                        }
                        IsAllow = true;
                        Koef = 2;
                        return;
                    }
                }

            
            }

            public int CompareTo(object obj)
            {
                var q = obj as IPokerHand;
                if (q == null) return 1;
                if (q.Koef != Koef) return Koef.CompareTo(q.Koef);
                if (!IsAllow && !q.IsAllow) return 0;
                if (!IsAllow && q.IsAllow) return 0;

                var qq = obj as Poker_OnePair;
                return qq == null ? 1 : StartCard.IntValue.CompareTo(qq.StartCard.IntValue);
            }

        }

        public class Poker_HighCard : PokerHand
        {
            public PokerCard StartCard { get; set; }

            public Poker_HighCard(ref List<PokerCard> cards)
            {
                IsAllow = false;
                Koef = 0;

                if (cards.Count < 1) return;
                StartCard = cards[cards.Count - 1];

                cards.Clear();
                IsAllow = true;
                Koef = 1;
            }

            public override int CompareTo(object obj)
            {
                var q = obj as IPokerHand;
                if (q == null) return 1;
                if (q.Koef != Koef) return Koef.CompareTo(q.Koef);
                if (!IsAllow && !q.IsAllow) return 0;
                if (!IsAllow && q.IsAllow) return 0;

                var qq = obj as Poker_HighCard;
                return qq == null ? 1 : StartCard.IntValue.CompareTo(qq.StartCard.IntValue);
            }

        }



        public static int GetHandResult(string[] hand)
        {
            if (hand.Length != 10) return 0;
            var player1 = new List<PokerCard>();
            var player2 = new List<PokerCard>();
            
            for (var i = 0; i < 5; i++ )
            {
                player1.Add(new PokerCard(hand[i]));
            }
            player1.Sort();
            
            for (var i = 5; i < 10; i++)
            {
                player2.Add(new PokerCard(hand[i]));
            }
            player2.Sort();

            var rf1 = new Poker_RoyalFlush(ref player1);
            var rf2 = new Poker_RoyalFlush(ref player2);
            if (rf1.CompareTo(rf2) != 0) return rf1.CompareTo(rf2);

            var sf1 = new Poker_StraightFlush(ref player1);
            var sf2 = new Poker_StraightFlush(ref player2);
            if (sf1.CompareTo(sf2) != 0) return sf1.CompareTo(sf2);

            var f1 = new Poker_FourOfKind(ref player1);
            var f2 = new Poker_FourOfKind(ref player2);
            if (f1.CompareTo(f2) != 0) return f1.CompareTo(f2);

            var fh1 = new Poker_FullHouse(ref player1);
            var fh2 = new Poker_FullHouse(ref player2);
            if (fh1.CompareTo(fh2) != 0) return fh1.CompareTo(fh2);

            var pf1 = new Poker_Flush(ref player1);
            var pf2 = new Poker_Flush(ref player2);
            if (pf1.CompareTo(pf2) != 0) return pf1.CompareTo(pf2);

            var s1 = new Poker_Straight(ref player1);
            var s2 = new Poker_Straight(ref player2);
            if (s1.CompareTo(s2) != 0) return s1.CompareTo(s2);

            var tk1 = new Poker_ThreeOfKind(ref player1);
            var tk2 = new Poker_ThreeOfKind(ref player2);
            if (tk1.CompareTo(tk2) != 0) return tk1.CompareTo(tk2);

            var tp1 = new Poker_TwoPairs(ref player1);
            var tp2 = new Poker_TwoPairs(ref player2);
            if (tp1.CompareTo(tp2) != 0) return tp1.CompareTo(tp2);

            var op1 = new Poker_OnePair(ref player1);
            var op2 = new Poker_OnePair(ref player2);
            if (op1.CompareTo(op2) != 0) return op1.CompareTo(op2);

            var hc1 = new Poker_HighCard(ref player1);
            var hc2 = new Poker_HighCard(ref player2);
            if (hc1.CompareTo(hc2) != 0) return hc1.CompareTo(hc2);

            return 0;
        }

        #endregion

        #region Interpolation

        public static List<long> GetContinuedFractions(long value)
        {
            long tmp = 0;
            return GetContinuedFractions(value, out tmp);
        }

        public static List<long> GetContinuedFractions(long value, out long count)
        {
            return GetContinuedFractions(value, out count, 1);
        }

        public static List<long> GetContinuedFractions(long value, out long count, long init)
        {
            count = 0;
            var a = new List<long>() {(long) Math.Truncate(Math.Sqrt(value))};
            var b = new List<Point>();
            if (Math.Sqrt(value) == Math.Truncate(Math.Sqrt(value))) return a;
            b.Add(new Point((int)init, -(int)a[0]));
            double sqrt = Math.Sqrt(value);

            while (true)
            {
                var c = (value - b[b.Count - 1].Y*b[b.Count - 1].Y)/b[b.Count - 1].X;

                a.Add((int) Math.Truncate((sqrt - b[b.Count - 1].Y)/c));
                var d = -b[b.Count - 1].Y - c*a[a.Count - 1];
                var tmp = new Point((int) c, (int) d);
                if (!b.Contains(tmp))
                {
                    b.Add(tmp);
                    continue;
                }
                count = b.Count - b.IndexOf(tmp);
                return a;
            }
        }

        public static void GetDivideByFractions(List<long> fractions, out string nom, out string denom)
        {
            GetDivideByFractions(fractions, out nom, out denom, fractions.Count-1);
        }

        public static void GetDivideByFractions(List<long> fractions, out string nom, out string denom, long count)
        {
            var index = count;
            if (index == 0)
            {
                nom = "1";
                denom = "1";
                return;
            }
            
            long tp = 0;
            denom = "1";
            nom = fractions[GetRealIndex(fractions.Count, (int)index)].ToString();
            while (index > 0)
            {
                index--;
                var tmp = SummString(MultipleString(nom, fractions[GetRealIndex(fractions.Count, (int)index)]), denom);
                denom = nom;
                nom = tmp;
            }
        }

        private static int GetRealIndex(int totalCount, int index)
        {
            if (index < totalCount) return index;
            return 1 + (index - 1)%(totalCount - 1);
        }

        #endregion

        #region Series

        public static List<long> GetFactors(long value)
        {
            long q = 0;
            return GetFactors(value, out q);
        }

        public static List<long> GetFactors(long value, out long summFactors)
        {
            var rs = new List<long>();
            summFactors = 0;
            var mid = Math.Sqrt(value);
            for (var i = 1; i < mid; i++)
            {
                if (value % i != 0) continue;
                rs.Add(i);
                rs.Add(value / i);
                summFactors += i;
                summFactors += value / i;
            }
            if (mid == Math.Truncate(mid))
            {
                rs.Add((long)mid);
                summFactors += (long)mid;
            }
            return rs;
        }

        private static Dictionary<long, int> GetPrimesForValue(long value)
        {
            var sqr = (long)Math.Sqrt(value)+1;
            var res = new Dictionary<long, int>();
            foreach (var l in GetPrimeList(sqr, true))
            {
                if (l > value) break;
                while (value % l == 0)
                {
                    if (!res.ContainsKey(l)) res.Add(l, 0);
                    res[l]++;
                    value /= l;
                }
            }
            if (value > 1) res.Add(value, 1);
            return res;
        }

        public static long Phi(long value)
        {
            if (value < 2) return 1;

            var pr = GetPrimesForValue(value);
            long rrs = 1;
            foreach (var pair in pr)
            {
                rrs *= pair.Key-1;
                for (var i = 1; i < pair.Value; i++)
                    rrs *= pair.Key;
            }
            return rrs;
        }

        public static List<long> GetAmicableChain(long value, long max, out long min)
        {
            min = value;
            var res = new List<long>(){value};
            if (value == 1)
            {
                return res;
            }
            while (true)
            {
                long tmp = 0;
                GetFactors(res[res.Count - 1], out tmp);
                tmp -= res[res.Count - 1];
                if (tmp > max) return new List<long>();
                if (tmp < min) min = tmp;
                if (tmp == 1)
                {
                    return new List<long>();
                }
                if (res.Contains(tmp))
                {
                    return value != tmp ? new List<long>() : res;
                }
                res.Add(tmp);
            }

        }

        public static List<long> FormeMinSet(long value)
        {
            var res = new List<long>();
            long sm = long.MaxValue;
            if (_minSet.Count == 0)
            {
                _minSet.Add(1, new List<long>(){1});
                _minSet.Add(2, new List<long>() { 1, 2 });
                _minSet.Add(3, new List<long>() { 2, 3, 4 });
                _minSet.Add(4, new List<long>() { 3, 5, 6, 7 });
                _minSet.Add(5, new List<long>() { 6, 9, 11, 12, 13 });
                _minSet.Add(6, new List<long>() { 11, 18, 19, 20, 22, 25 });
            }
            if (_minSet.ContainsKey(value)) return _minSet[value];
            FormeMinSetRec(ref res, ref sm, value, new List<long>());
            _minSet.Add(value,res);
            return res;
        }

        private static readonly Dictionary<long, List<long>> _minSet = new Dictionary<long, List<long>>();

        private static void FormeMinSetRec(ref List<long> result, ref long min, long value, List<long> current)
        {
            if (current.Count == 0 && value > 1 && _minSet.ContainsKey(value-1))
            {
                var qqq = new List<long>(_minSet[value-1]);
                var idx = qqq.Count/2;
                var b = qqq[idx];
                qqq.Insert(0, 0);
                min = 0;
                for(var i = 0; i < qqq.Count; i++)
                {
                    qqq[i] += b;
                    min += qqq[i];
                }
                result = qqq;
            }
            if (current.Count > value) return;
            var sm = GetSummOfSet(current);
            if (sm >= min) return;
            if (current.Count == value)
            {
                if (IsSetOptim(current))
                {
                    result = current;
                }
                return;
            }
            if (!IsSetOptim(current)) return;
            var start = current.Count > 0?current[current.Count - 1] + 1:value-1;
            var cnt = value - current.Count;
            var pr = cnt*(cnt-1)/2+sm;
            for (var cr = start; cr < (min-pr)/(double)cnt; cr++)
            {
                var tmp = new List<long>(current) {cr};
                FormeMinSetRec(ref result, ref min, value, tmp);
            }
        }

        public static bool IsSetOptim(List<long> lst)
        {
            if (lst.Count <= 2) return true;
            var tmp = FormeSets(lst);

            for (var i = 0; i < tmp.Count - 1; i++ )
            {
                var s1 = GetSummOfSet(tmp[i]);
                for (var j = i+1; j < tmp.Count;j++)
                {
                    var s2 = GetSummOfSet(tmp[j]);
                    if (tmp[i].Count == tmp[j].Count)
                    {
                        if (s1 == s2) return false;
                        continue;
                    }
                    if (Math.Sign(s1-s2) != Math.Sign(tmp[i].Count-tmp[j].Count)) return false;
                }
            }
            return true;
        }

        private static List<List<long>> FormeSets(List<long> leaved)
        {
            var result = new List<List<long>>();
            var prev = new List<List<long>>();
            foreach (var l in leaved)
            {
                prev.Add(new List<long>(){l});
            }
            result.AddRange(prev);
            var index = 0;
            while (index < leaved.Count-2)
            {
                index++;
                var tmp = new List<List<long>>();
                foreach (var list in prev)
                {
                    for (var i = leaved.Count - 1; i >= 0; i-- )
                    {
                        if (leaved[i] <= list[list.Count - 1]) break;
                        tmp.Add(new List<long>(list){leaved[i]});
                    }
                }
                result.AddRange(tmp);
                prev = new List<List<long>>(tmp);
            }
            return result;
        }

        public static long GetSummOfSet(List<long> lst)
        {
            long res = 0;
            foreach (var l in lst)
            {
                res += l;
            }
            return res;
        }

        #endregion

        #region Roman numbers

        private enum RomanDigit
        {
            I = 1,
            V = 5,
            X = 10,
            L = 50,
            C = 100,
            D = 500,
            M = 1000
        }

        public static long RomanToNumber(string roman)
        {
            roman = roman.ToUpper().Trim();

            long cur = 0;
            long res = 0;
            long prev = 0;

            foreach (var c in roman)
            {
                var tmp = (int) Enum.Parse(typeof (RomanDigit), c.ToString());
                if (prev == 0) prev = tmp;
                if (tmp > prev)
                {
                    res += tmp - cur;
                    prev = tmp;
                    cur = 0;
                    continue;
                }
                if (tmp == prev)
                {
                    cur += tmp;
                    continue;
                }
                res += cur;
                prev = tmp;
                cur = tmp;
            }
            if (cur != 0) res += cur;
            return res;
        }

        public static string NumberToRoman(long number)
        {
            if (number == 0) return "N";

            var values = new [] { 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 };
            var numerals = new [] { "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I" };

            var result = new StringBuilder();

            for (var i = 0; i < 13; i++)
            {
                while (number >= values[i])
                {
                    number -= values[i];
                    result.Append(numerals[i]);
                }
            }

            return result.ToString();
        }



        #endregion

        #region Sets

        public static bool IsEqual(ICollection<long> value1, ICollection<long> value2)
        {
            if (value1.Count != value2.Count) return false;
            var hs1 = new HashSet<long>(value1);
            var hs2 = new HashSet<long>(value2);
            return hs1.IsSubsetOf(hs2) && hs2.IsSubsetOf(hs1);
        }

        #endregion

        #region Chains

        public static List<string> GetChains(string value)
        {
            var res = new List<string>(){value};
            var cur = "0";
            while (true)
            {
                cur = "0";
                foreach (var c in res[res.Count-1])
                {
                    cur = SummString(cur, ((c - 48) * (c - 48)).ToString());
                }
                if (res.Contains(cur))
                {
                    res.Add(cur);
                    return res;
                }
                res.Add(cur);
            }

        }

        public static List<ulong> GetChains(ulong value)
        {
            var res = new List<ulong>() { value };
            while (true)
            {
                ulong cur = 0;
                var vl = res[res.Count - 1];
                while (vl > 0)
                {
                    cur += (vl%10)*(vl%10);
                    vl /= 10;
                }
                res.Add(cur);
                if (cur == 1 || cur == 89) return res;
            }

        }

        #endregion

        #region Sudocu

        public static List<byte[][]> SolveSudocu(byte[][] value)
        {
            return SolveSudocu(value, long.MaxValue);
        }

        public static List<byte[][]> SolveSudocu(byte[][] value, long maxSol)
        {
            var init = new HashSet<byte>[value.Length][];
            for (var y = 0; y < value.Length; y++)
            {
                init[y] = new HashSet<byte>[value[y].Length];
                for (var x = 0; x < value[y].Length;x++)
                {
                    init[y][x] = new HashSet<byte>();
                    if (value[y][x] > 0) init[y][x].Add(value[y][x]);
                    else
                    {
                        for (byte i = 1; i < 10; i++)
                        {
                            init[y][x].Add(i);
                        }

                        for (byte i = 1; i < 10; i++)
                        {
                            if (value[y][i-1] > 0) init[y][x].Remove(value[y][i-1]);
                            if (value[i-1][x] > 0) init[y][x].Remove(value[i-1][x]);
                            if (value[3*(y / 3) + ((i - 1) / 3)][3*(x / 3) + ((i - 1) % 3)] > 0)
                                init[y][x].Remove(value[3 * (y / 3) + ((i - 1) / 3)][3 * (x / 3) + ((i - 1) % 3)]);
                        }
                    }
                }
            }
            var res = new List<byte[][]>();
            SudocuRec(res, init, maxSol);
            return res;
        }

        private static void SudocuRec(ICollection<byte[][]> result, HashSet<byte>[][] current, long maxSol)
        {
            if (result.Count >= maxSol) return;
            var x = -1;
            var y = -1;
            for (var my = 0; my < current.Length; my++)
            {
                for (var mx = 0; mx < current[my].Length; mx++)
                {
                    if (current[my][mx].Count <= 0) return;
                    if (current[my][mx].Count <= 1 || x != -1) continue;
                    x = mx;
                    y = my;
                }
            }

            if (x == -1 && y == -1)
            {
                var qq = GetArray(current);
                if (!ProveArray(qq)) return;
                result.Add(GetArray(current));
                return;
            }
  
            foreach (var b in current[y][x])
            {
                var tmp = CopyArray(current);
                for (byte i = 1; i < 10; i++)
                {
                    //if (tmp[y][i - 1].Contains(b))
                        tmp[y][i-1].Remove(b);
                    //if (tmp[i - 1][x].Contains(b))
                        tmp[i - 1][x].Remove(b);
                    //if (tmp[3 * (y / 3) + ((i - 1) / 3)][3 * (x / 3) + ((i - 1) % 3)].Contains(b))
                        tmp[3 * (y / 3) + ((i - 1) / 3)][3 * (x / 3) + ((i - 1) % 3)].Remove(b);
                    
                }
                tmp[y][x] = new HashSet<byte>() { b };
                SudocuRec(result, tmp, maxSol);
            }
        }

        private static bool ProveArray(byte[][] array)
        {
            for (var y = 0; y < 9; y++)
            {
                var hsX = new HashSet<byte>();
                var hsY = new HashSet<byte>();
                var hsD = new HashSet<byte>();
                for (var x = 0; x < 9; x++)
                {
                    var tmp = array[y][x];
                    if (hsY.Contains(tmp)) return false;
                    hsY.Add(tmp);

                    tmp = array[x][y];
                    if (hsX.Contains(tmp)) return false;
                    hsX.Add(tmp);

                    tmp = array[3*(y/3) + (x/3)][3*(y%3) + (x%3)];
                    if (hsD.Contains(tmp)) return false;
                    hsD.Add(tmp);
                }
            }
            return true;
        }

        private static byte[][] GetArray(HashSet<byte>[][] array)
        {
            var res = new byte[array.Length][];

            for (var y = 0; y < array.Length; y++)
            {
                res[y] = new byte[array[y].Length];
                for (var x = 0; x < res[y].Length; x++)
                {
                    foreach (var re in array[y][x])
                    {
                        res[y][x] = re;
                    }
                }
            }
            return res;
        }

        private static HashSet<byte>[][] CopyArray(HashSet<byte>[][] array)
        {
            var res = new HashSet<byte>[array.Length][];

            for (var y = 0; y < array.Length; y++)
            {
                res[y] = new HashSet<byte>[array[y].Length];
                for (var x = 0; x < res[y].Length; x++)
                {
                    var tmp = new HashSet<byte>(array[y][x]);
                    res[y][x] = tmp;
                }
            }
            return res;
        }

        #endregion

        #region Geometry

        public static bool IsContainsPoint(Point[] array, Point origin)
        {
            if (array == null || array.Length <= 2) return false;
  
              var j = array.Length - 1;
              var c = false;
              for (var i = 0; i < array.Length;i++)
              {
                  if ((((array[i].Y<=origin.Y) && (origin.Y<array[j].Y)) || ((array[j].Y<=origin.Y) && (origin.Y<array[i].Y))) &&
                  (origin.X > (array[j].X - array[i].X) * (origin.Y - array[i].Y) / (array[j].Y - array[i].Y) + array[i].X))
                  {
                      c = !c;
                  }
                  j = i;
              }
            return c;
         }

        #endregion

        #region Network

        public class Edge : IComparable
        {
            public Point Vertex { get; set; }
            public long Weight { get; set; }

            public Edge(Point vertex, long weight)
            {
                Vertex = vertex;
                Weight = weight;
            }

            public int CompareTo(object obj)
            {
                var tmp = obj as Edge;
                return tmp == null ? 1 : Weight.CompareTo(tmp.Weight);
            }
        }

        public static bool IsCycle(List<Edge> edges)
        {
            var hs = new HashSet<int>();
            foreach (var edge in edges)
            {
                if (!hs.Contains(edge.Vertex.X))
                {
                    if (IsCyclePoint(edges, edge.Vertex.X))
                        return true;
                    hs.Add(edge.Vertex.X);
                }
                if (!hs.Contains(edge.Vertex.Y))
                {
                    if (IsCyclePoint(edges, edge.Vertex.Y))
                        return true;
                    hs.Add(edge.Vertex.Y);
                }
            }
            return false;
        }

        //public static bool IsCycle(List<Edge> edges, Edge added)
        //{
        //    var tmp = new List<Edge>() {added};
        //    if (IsCyclePoint(tmp, added.Vertex.X)) return true;
        //    if (IsCyclePoint(tmp, added.Vertex.Y)) return true;
            
        //    return false;
        //}


        private static bool IsCyclePoint(List<Edge> edges, int start)
        {
            var res = new List<List<int>>(){new List<int>(){start}};
            int cnt = 0;
            while (true)
            {
                cnt++;
                var pr = new List<List<int>>();
                foreach (var re in res)
                {
                    if (re.Count != cnt) continue;
                    foreach (var edge in edges)
                    {
                        var tmp = -1;
                        var prev = -1;
                        if (re[cnt-1] == edge.Vertex.X)
                        {
                            tmp = edge.Vertex.Y;
                            prev = edge.Vertex.X;
                        }
                        if (re[cnt-1] == edge.Vertex.Y)
                        {
                            tmp = edge.Vertex.X;
                            prev = edge.Vertex.Y;
                        }
                        if (tmp == -1) continue;
                        if (cnt>1)
                        {
                            if (re[cnt-2] == tmp)
                                continue;
                            if (re.Contains(tmp))
                                return true;
                        }
                        pr.Add(new List<int>(re){tmp});
                    }
                }
                if (pr.Count == 0) return false;
                res.AddRange(pr);
            }
            
            
        }

        public static long GetSummOfEdges(List<Edge> edges)
        {
            long res = 0;
            foreach (var edge in edges)
            {
                res += edge.Weight;
            }
            return res;
        }

        #endregion

        #region Darth

        private static long GetDarthScore(long index)
        {
            if (index == -1) return 0;
            var mult = index/21;
            var idx = index%21;
            if (idx == 20) idx = 24;
            idx++;
            mult++;
            return mult*idx;
        }

        public static Dictionary<long, long> GetDiffersDarth()
        {
            var res = new Dictionary<long, long>();

            for (var i1 = -1; i1 <= 61; i1++)
            {
                for (var i2 = i1; i2 <= 61; i2++)
                {
                    for (var i3 = 21; i3 <= 41; i3++)
                    {
                        var tmp = GetDarthScore(i1) + GetDarthScore(i2) + GetDarthScore(i3);
                        if (!res.ContainsKey(tmp)) res.Add(tmp, 0);
                        res[tmp]++;
                    }
                }
            }

            return res;
        }

        #endregion

        #region Diaphant

        public static long GetDiaphantCountSolution(long n)
        {
            var tmp = MathLogic.GetPrimeFactors(n);
            long res = 1;
            foreach (var pair in tmp)
            {
                res *= (2 * pair.Value + 1);
            }
            return (res - 1) / 2 + 1;
        }

        public static long GetMaxNDiaphant(long maxCount)
        {
            var res = new List<long>();
            var mx = long.MaxValue;
            FormeDiaphantRec(ref res, ref mx, maxCount, new List<long>(), 1);
            return mx;
        }

        private static void FormeDiaphantRec(ref List<long> result, ref long mx, long max, List<long> current, long cur)
        {
            var qqq = GetValueForDiaphant(current);
            if (qqq >= mx) return;
            if (cur > 2 * max - 1)
            {
                mx = qqq;
                result = current;
                return;
            }

            for (var i = 1; i <= ((current.Count > 0) ? current[current.Count - 1] : max / cur); i++)
            {
                var tmp = new List<long>(current) { i };
                FormeDiaphantRec(ref result, ref mx, max, tmp, cur * (2 * i + 1));
            }

        }



        private static long GetValueForDiaphant(IEnumerable<long> vals)
        {
            long res = 1;
            var tmp = new List<long>(vals);
            tmp.Sort();
            tmp.Reverse();
            var qq = MathLogic.GetPrimeList(tmp.Count);
            for (var i = 0; i < qq.Count; i++)
            {
                if (tmp[i] * Math.Log(qq[i]) >= Math.Log(long.MaxValue / (double)res)) return long.MaxValue;
                res *= (long)Math.Pow(qq[i], tmp[i]);
            }
            return res;
        }

        #endregion

        public static long GetANotForPrimes(long val, long max)
        {
            if (val % 5 == 0 || val % 2 == 0) return -1;
            if (IsPrimeNumber(val)) return -1;
            long x = 1;
            long k = 1;
            while (x != 0)
            {
                x = (10 * x + 1) % val;
                k++;
                if (k > max + 1)
                    return k;
            }
            return k;
        }

        public static long GetAForPrimes(long val, long max)
        {
            if (val % 5 == 0 || val % 2 == 0) return -1;
            if (!IsPrimeNumber(val)) return -1;
            long x = 1;
            long k = 1;
            while (x != 0)
            {
                x = (10 * x + 1) % val;
                k++;
                if (k >= max)
                    return k;
            }
            return k;
        }

        public static bool IsExactA(long val, long max)
        {
            if (val % 5 == 0 || val % 2 == 0) return false;
            long x = 1;
            long k = 1;
            while (k < max)
            {
                x = (10 * x + 1) % val;
                k++;
                if (x == 0 && max %k == 0)
                    return true;
            }
            return x ==0;
        }

        public static long GetA(long val, long max)
        {
            if (val % 5 == 0 || val % 2 == 0) return -1;
            long x = 1;
            long k = 1;
            while (x != 0)
            {
                x = (10 * x + 1) % val;
                k++;
                if (k > max + 1)
                    return k;
            }
            return k;
        }

    }
    
}
